// SPDX-License-Identifier: Apache-2.0
import { intersectLineLine } from "@thi.ng/geom-isec/line-line";
import { centroid } from "@thi.ng/geom-poly-utils/centroid";
import { EPS } from "@thi.ng/math/api";
import type { ReadonlyVec, Vec } from "@thi.ng/vectors";
import { corner2 } from "@thi.ng/vectors/clockwise";

/**
 * Extended version of Sutherland-Hodgeman convex polygon clipping supporting
 * any convex boundary polygon (not only rects). Returns new array of clipped
 * vertices.
 *
 * https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
 *
 * @param pts - subject poly vertices
 * @param bounds - clipping boundary vertices
 * @param bc - pre-computed boundary centroid
 * @param eps - edge classification tolerance
 */
export const sutherlandHodgeman = (
	pts: ReadonlyVec[],
	bounds: ReadonlyVec[],
	bc?: ReadonlyVec,
	eps = EPS
) => {
	bc = bc || centroid(bounds);
	for (let ne = bounds.length, j = ne - 1, i = 0; i < ne; j = i, i++) {
		const clipped: Vec[] = [];
		const ca = bounds[j];
		const cb = bounds[i];
		const sign = corner2(ca, cb, bc, eps);
		for (let np = pts.length, k = np - 1, l = 0; l < np; k = l, l++) {
			const p = pts[k];
			const q = pts[l];
			const cqsign = corner2(ca, cb, q, eps);
			if (corner2(ca, cb, p, eps) === sign) {
				clipped.push(
					cqsign !== sign
						? intersectLineLine(ca, cb, p, q).isec![0]
						: q
				);
			} else if (cqsign === sign) {
				clipped.push(intersectLineLine(ca, cb, p, q).isec![0], q);
			}
		}
		if (clipped.length < 2) {
			return [];
		}
		pts = clipped;
	}
	return pts;
};
